The present invention relates to methods and apparatus for compressing and expanding digitized images.
A digitized image comprises picture elements or pixels, each expressed by a certain number of bits of data. Each pixel of a black-and-white image is expressed by just one bit. In a color image, or an image consisting of black, white, and shades of gray, each pixel is expressed by plural bits. As the number of pixels in the image (the image resolution) and the number of bits per pixel (the pixel depth) are increased to improve the quality of the image, the amount of pixel data becomes extremely large, requiring much memory space for storage and much time for transmission. To reduce these requirements, images are frequently compressed by various types of coding.
In one conventional coding method, two consecutive lines of image data are compared. If the two lines of data are identical, an entire line of data can be compressed to a single flag value indicating that the line is identical to the preceding line. In a variation of this conventional method, each line is divided into blocks of consecutive pixels, and each block is compared with the corresponding block in the preceding line, instead of comparing an entire line at a time.
A drawback of these conventional coding methods is that when the two compared lines or blocks are not identical, the data are not compressed at all. Even a minor difference between the two lines or blocks can prevent compression. For most images, the compression ratio is accordingly rather low, especially when the number of pixels per block or line is large, or the pixel depth is large.